Search for: All records

Label Propagation is not only a well-known machine learning algorithm for classification, but it is also an effective method for discovering communities and connected components in networks. We propose a new Direction-Optimizing Label Propagation Algorithm (DOLPA) framework that enhances the performance of the standard Label Propagation Algorithm (LPA), increases its scalability, and extends its versatility and application scope. As a central feature, the DOLPA framework relies on the use of frontiers and alternates between label push and label pull operations to attain high performance. It is formulated in such a way that the same basic algorithm can be used for finding communities or connected components in graphs by only changing the objective function used. Additionally, DOLPA has parameters for tuning the processing order of vertices in a graph to reduce the number of edges visited and improve the quality of solution obtained. We present the design and implementation of the enhanced algorithm as well as our shared-memory parallelization of it using OpenMP. We also present an extensive experimental evaluation of our implementations using the LFR benchmark and real-world networks drawn from various domains. Compared with an implementation of LPA for community detection available in a widely used network analysis software, we achieve at most five times the F-Score while maintaining similar runtime for graphs with overlapping communities. We also compare DOLPA against an implementation of the Louvain method for community detection using the same LFR-graphs and show that DOLPA achieves about three times the F-Score at just 10% of the runtime. For connected component decomposition, our algorithm achieves orders of magnitude speedups over the basic LP-based algorithm on large diameter graphs, up to 13.2 × speedup over the Shiloach-Vishkin algorithm, and up to 1.6 × speedup over Afforest on an Intel Xeon processor using 40 threads. 

The modes of Pacific decadal-scale variability (PDV), traditionally defined as statistical patterns of variance, reflect to first order the ocean's integration (i.e., reddening) of atmospheric forcing that arises from both a shift and a change in strength of the climatological (time-mean) atmospheric circulation. While these patterns concisely describe PDV, they do not distinguish among the key dynamical processes driving the evolution of PDV anomalies, including atmospheric and ocean teleconnections and coupled feedbacks with similar spatial structures that operate on different timescales. In this review, we synthesize past analysis using an empirical dynamical model constructed from monthly ocean surface anomalies drawn from several reanalysis products, showing that the PDV modes of variance result from two fundamental low-frequency dynamical eigenmodes: the North Pacific–central Pacific (NP-CP) and Kuroshio–Oyashio Extension (KOE) modes. Both eigenmodes highlight how two-way tropical–extratropical teleconnection dynamics are the primary mechanisms energizing and synchronizing the basin-scale footprint of PDV. While the NP-CP mode captures interannual- to decadal-scale variability, the KOE mode is linked to the basin-scale expression of PDV on decadal to multidecadal timescales, including contributions from the South Pacific. 

Coral reefs are home to the greatest diversity of marine life, and many species on reefs live in symbiotic associations. Studying the historical biogeography of symbiotic species is key to unravelling (potential) coevolutionary processes and explaining species richness patterns. Coral-dwelling gall crabs (Cryptochiridae) live in obligate symbiosis with a scleractinian host, and are ideally suited to study the evolutionary history between heterogeneous taxa involved in a symbiotic relationship. The genus Opecarcinus Kropp and Manning, 1987, like its host coral family Agariciidae, occurs in both Indo-Pacific and Caribbean seas, and is the only cryptochirid genus with a circumtropical distribution. Here, we use mitochondrial and nuclear DNA gene fragments of Opecarcinus specimens sampled from 21 Indo-Pacific localities and one Atlantic (Caribbean) locality. We applied several species delimitation tests to characterise species diversity, inferred a Bayesian molecular-clock time-calibrated phylogeny to estimate divergence times and performed an ancestral area reconstruction. Time to the most recent common ancestor (tMRCA) of Opecarcinus is estimated at 15−6 Mya (middle Miocene—late Miocene). The genus harbours ~ 15 undescribed species as well as several potential species complexes. There are indications of strict host-specificity patterns in certain Opecarcinus species in the Indo-Pacific and Atlantic, however, a robust phylogeny reconstruction of Agariciidae corals—needed to test this further—is currently lacking. The Indo-West Pacific was inferred to be the most probable ancestral area, from where the Opecarcinus lineage colonised the Western Atlantic and subsequently speciated into O. hypostegus. Opecarcinus likely invaded from the Indo-West Pacific across the East Pacific Barrier to the Atlantic, before the full closure of the Isthmus of Panama. The subsequent speciation of O. hypostegus, is possibly associated with newly available niches in the Caribbean, in combination with genetic isolation following the closure of the Panama Isthmus.